/*
3249. 统计好节点的数目 https://leetcode.cn/problems/count-the-number-of-good-nodes/
中等  2024/11/19 解答错误 478 / 620 个通过的测试用例
*/
class Solution {
public:
    // 定义一个成员变量来存储树的邻接表
    vector<vector<int>> adj;
    
    // 定义一个递归的DFS函数，计算每个节点的子树大小
    int dfs(int node, int parent, vector<int>& subtreeSize, vector<int>& goodNodes) {
        unordered_map<int, int> sizeCount;  // 记录子树大小的频次
        subtreeSize[node] = 1;  // 当前节点本身就是一个子树

        for (int child : adj[node]) {
            if (child == parent) continue;  // 防止回到父节点
            int childSize = dfs(child, node, subtreeSize, goodNodes);
            subtreeSize[node] += childSize;  // 累加子树大小

            sizeCount[childSize]++;  // 记录当前子节点的子树大小
        }

        // 判断当前节点是否是一个好节点
        if (sizeCount.size() == 1) {
            goodNodes[node] = 1;  // 是好节点
        }

        return subtreeSize[node];
    }

    int countGoodNodes(vector<vector<int>>& edges) {
        int n = edges.size() + 1;  // 节点的数量
        adj.resize(n);

        // 构造邻接表
        for (const auto& edge : edges) {
            int u = edge[0], v = edge[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        vector<int> subtreeSize(n, 0);  // 存储每个节点的子树大小
        vector<int> goodNodes(n, 0);    // 记录好节点，1表示是好节点

        // 从根节点0开始DFS遍历树
        dfs(0, -1, subtreeSize, goodNodes);

        // 统计好节点的数量
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (goodNodes[i] == 1) {
                result++;
            }
        }

        return result;
    }
};